package com.my.study.structures.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * @author Carlos
 * @version 1.0
 * @Description 逆波兰计算器实现
 * @date 2021/6/23 22:30
 **/
public class PolandNotationCalculator{

    /**
     * 匹配多位数字
     */
    private static final String PATTERN_NUMBER = "\\d+";

    /**
     * 空格
     */
    private static final String DEFAULT_SPACE = " ";


    /**
     * 逆波兰表达式
     * <p>
     * 每个字符使用空格隔开:
     * (3+4)*5-6 -> 3 4 + 5 * 6 -
     * </p>
     */
    private final String suffixExpression;

    private List<String> suffixList;

    private Stack<String> suffixStack;

    public PolandNotationCalculator(String suffixExpression) {
        this.suffixExpression = suffixExpression;
        this.suffixList = initSuffixList(new MiddleToAfterConverter(this.suffixExpression).transfer());
        this.suffixStack = new Stack<>();
    }

    /**
     * 初始化list
     *
     * @param suffixExpression 表达式
     * @return List
     */
    private List<String> initSuffixList(String suffixExpression) {
        return Arrays.stream(suffixExpression.split(DEFAULT_SPACE)).collect(Collectors.toList());
    }

    /**
     * 计算
     *
     * @return 最终返回的结果
     */
    public int calculator() {
        for (String item : suffixList) {
            // 是数字，入栈
            if (isNumber(item)) {
                suffixStack.push(item);
            }
            // 是符号，从栈弹出两个数，计算结果再入栈
            else {
                // beforeNum为第一个数，栈顶；afterNum为第二个数，次栈顶
                // 对于减号和除号运算符，需要afterNum - beforeNum、afterNum / beforeNum
                int beforeNum = Integer.parseInt(suffixStack.pop());
                int afterNum = Integer.parseInt(suffixStack.pop());
                suffixStack.push("" + calResult(afterNum, beforeNum, item));
            }
        }

        return Integer.parseInt(suffixStack.pop());
    }

    /**
     * 判断是否为数字
     *
     * @param item
     * @return
     */
    private boolean isNumber(String item) {
        return item.matches(PATTERN_NUMBER);
    }

    /**
     * 计算
     *
     * @param afterNum
     * @param beforeNum
     * @param item
     * @return
     */
    private int calResult(int afterNum, int beforeNum, String item) {
        int result;
        switch (item) {
            case "+":
                result = afterNum + beforeNum;
                break;
            case "-":
                result = afterNum - beforeNum;
                break;
            case "*":
                result = afterNum * beforeNum;
                break;
            case "/":
                result = afterNum / beforeNum;
                break;
            default:
                throw new RuntimeException("运算符号有误 [" + item + "]" );
        }

        return result;
    }


    public String getSuffixExpression() {
        return suffixExpression;
    }

    public List<String> getSuffixList() {
        return suffixList;
    }



    /**
     * 中缀表达式转化后缀表达式实现类
     * <p>
     * 具体实现：
     *    1、初始化两个栈，运算符栈s1和存储中间结果栈s2;
     *    2、从左到右扫描；
     *    3、遇到操作数时，压入s2;
     *    4、遇到运算符，与s1栈顶运算符优先级进行比较：
     *      1) 如果s1为空，或者s1栈顶运算符为左括号"("，则直接将当前运算符入s1栈;
     *      2) 否则，若优先级比s1栈顶运算符高，也将当前运算符压入s1栈；
     *      3) 否则，将s1栈顶运算符弹出并压入s2中，再次循环(4-1)与s1新栈顶运算符进行比较；
     *    5、遇到括号时：
     *      1) 如果是左括号"("，直接压入s1栈；
     *      2) 如果是右括号")"，则依次弹出s1栈顶运算符并压入s2，直到遇到左括号")"为止，此时将这对括号舍弃
     *    6、重复步骤2至5，直到表达式最右边；
     *    7、将s1中剩余的运算符依次弹出压入s2；
     *    8、依次从s2弹出元素，其结果的逆序就是后缀表达式
     * </p>
     */
    final static class MiddleToAfterConverter extends AbstractStringTransform {

        private static final int ASCII_MIN_NUMBER = 48;

        private static final int ASCII_MAX_NUMBER = 57;

        /**
         * 中缀表达式
         */
        private String infixExpression;

        /**
         * 运算符栈 s1
         */
        private Stack<String> operatorStack;

        /**
         * 存储中间结果栈s2 -> 因为没有弹栈操作，可以使用List集合代替
         */
        private List<String> tempResultList;


        MiddleToAfterConverter(String infixExpression) {
            this.infixExpression = infixExpression;
            this.operatorStack = new Stack<>();
            this.tempResultList = new ArrayList<>();
        }

        public String transfer() {
            return transfer(this.infixExpression);
        }

        /**
         * 中缀表达式转化为后缀表达式
         *
         * @param express
         * @return
         */
        @Override
        public String transfer(String express) {
            List<String> list = toFixList(express);
            // 遍历
            for (String item : list) {
                // 1.是数字
                if (item.matches(PATTERN_NUMBER)) {
                    tempResultList.add(item);
                }
                // 2.是左括号
                else if ("(".equals(item)){
                    operatorStack.push(item);
                }
                // 3.是右括号
                else if (")".equals(item)) {
                    // 如果是")"右括号，则依次从operatorStack栈顶弹出运算符并压入tempResultList，直到遇到"("
                    // 丢弃一对括号
                    while (!"(".equals(operatorStack.peek())) {
                        tempResultList.add(operatorStack.pop());
                    }
                    // 弹出"("左括号！！！！
                    operatorStack.pop();
                }
                // 4、运算符
                else {
                    String temp;
                    // 当item的运算符优先级<=s1栈顶的有运算符，将s1栈顶元素压入s2
                    while (operatorStack.size() != 0
                            && !"(".equals(temp = operatorStack.peek())
                            && getPriorityValue(item) <= getPriorityValue(temp)) {
                        tempResultList.add(operatorStack.pop());
                    }
                    operatorStack.push(item);
                }
            }

            // 将s1全部压入s2
            while (operatorStack.size() != 0) {
                tempResultList.add(operatorStack.pop());
            }

            return String.join(" ", tempResultList);
        }

        /**
         * 判断是否为字符
         *
         * @param c 字符
         * @return
         */
        private boolean isSign(char c) {
            return c < ASCII_MIN_NUMBER || c > ASCII_MAX_NUMBER;
        }

        /**
         * 判断是否为数字
         *
         * @param c 字符
         * @return
         */
        private boolean isNumber(char c) {
            return c >= ASCII_MIN_NUMBER && c <= ASCII_MAX_NUMBER;
        }

        /**
         * 将字符串中缀表达式转化为集合中缀表达式
         * <p>
         *     "1+2-3" -> [1,2,+,3,-]
         * </p>
         *
         * @return List
         */
        List<String> toFixList(String expression) {
            int i = 0,length;
            char c;
            StringBuilder sb = new StringBuilder();
            length = expression.length();
            List<String> fixList = new ArrayList<>();
            do {
                if (isSign((c = expression.charAt(i)))) {
                    fixList.add(String.valueOf(c));
                    i++;
                }
                else {
                    sb.setLength(0);
                    while (i < length && isNumber((c = expression.charAt(i)))) {
                        sb.append(c);
                        i++;
                    }
                    fixList.add(sb.toString());
                }
            } while (i < length);

            return fixList;
        }

        String getInfixExpression() {
            return infixExpression;
        }

        List<String> getTempResultList() {
            return tempResultList;
        }
    }
}
